﻿#include <stdio.h>
#include <stdlib.h>
#include <iostream>

#define MaxTreeSize 10
typedef char TElemType;

typedef struct BiTNode {
    TElemType data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

void InitTree(BiTree &BT) {
    BT = NULL;
}

void CreateBiTree(BiTree &BT) {
    TElemType e;
    std::cin >> e;
    if (e == '#')
        e = NULL;
    else {
        BT = (BiTNode *) malloc(sizeof(BiTNode));
        if (!BT) exit(-1);
        BT->data = e;
        CreateBiTree(BT->lchild);
        CreateBiTree(BT->rchild);
    }
}

void Visit(BiTree BT) {
    std::cout << BT->data;
}


int TreeDepth(BiTree BT) {
    int Lh, Rh;
    if (!BT) return 0;
    Lh = TreeDepth(BT->lchild);
    Rh = TreeDepth(BT->rchild);
    return Lh > Rh ? Lh + 1 : Rh + 1;
}


void PreOrder(BiTree BT) {
    if (BT) {
        Visit(BT);
        PreOrder(BT->lchild);
        PreOrder(BT->rchild);
    }
}

/*
 * 设树B是一棵采用链式结构存储的二叉树，编写一个把树B中所有结点的左、右子树进行交换的函数。
 * 操作步骤：可以递归实现？lp指向左子树，rp指向右子树
 */
void Swap(BiTree &BT) {
    if (BT) {
        Swap(BT->lchild);
        Swap(BT->rchild);
        BiTNode *temp;
        temp = BT->lchild;
        BT->lchild = BT->rchild;
        BT->rchild = temp;
    }
}


int main() {
    BiTree BT;
    InitTree(BT);
    printf("创建一棵二叉树,请按照前序序列输入树中的结点（'#'表示子树为空）：\n");
    CreateBiTree(BT);

    std::cout << "左右子树进行交换";
    Swap(BT);

    std::cout << "交换后先序遍历序列为：";
    PreOrder(BT);

    return 0;
}